Khu vực mà hiện nay là quảng trường Đỏ thì trước đây là các công trình xây dựng bằng gỗ, nhưng đã bị phá bỏ đi theo sắc lệnh của Đại công tước Ivan III năm 1493, do các công trình này rất dễ bị cháy. Khu vực mới tạo ra (trước đó đơn giản gọi là Pozhar, tức "khu vực cháy") dần dần chuyển thành như là nơi diễn ra các hoạt động thương mại chủ yếu của Moskva. Tên gọi khi đó là Torgovaya nghĩa là quảng trường thương mại. Sau đó, nó được sử dụng cho nhiều lễ nghi công cộng khác nhau cũng như thỉnh thoảng làm nơi diễn ra lễ đăng quang của các Sa hoàng Nga. Quảng trường đã dần dần được xây dựng từ thời điểm đó, và nó được sử dụng cho các nghi lễ chính thức của tất cả các chính quyền Nga kể từ khi nó được xây dựng.

Tên gọi quảng trường Đỏ không có nguồn gốc từ màu sắc của gạch bao quanh nó hay từ sự liên hệ giữa màu đỏ và chủ nghĩa cộng sản. Nó bắt nguồn từ tên gọi trong tiếng Nga красная (krasnaya) có thể mang nghĩa "đỏ" hay "đẹp" (nghĩa sau là nghĩa cổ, nay không dùng). Từ này ban đầu được dùng để chỉ (với nghĩa "đẹp") nhà thờ thánh Basil, và sau đó dần dần được chuyển để chỉ quảng trường cạnh đó. Người ta tin rằng quảng trường này có tên gọi như hiện nay (thay thế cho tên gọi Pozhar cũ) vào nửa sau thế kỷ 17 với nghĩa "đẹp". Chỉ từ thế kỷ 19 thì từ này mới mang nghĩa đỏ cho đến ngày nay. Một số thành thị Nga cổ, chẳng hạn Suzdal, Yelets hay Pereslavl-Zalessky, cũng có quảng trường chính của mình mang tên Krasnaya ploshchad, trùng tên với quảng trường Đỏ của Moskva.